This invention relates to a packet scheduler, for use in allocating network resources to different sources of data traffic.
In a communications network, a connection between two network nodes (a source node and a destination node) has a predetermined bandwidth. That is, there is a maximum amount of data that the connection can handle in any particular time period.
The source node may be attempting to transmit data of different types, or from different originating devices. In that case, it is necessary to determine how the available bandwidth should be shared between the different types of data or the data from the different originating devices.
Many different methods have been proposed for determining how to allocate this available bandwidth. A common problem is to maximize the efficiency with which the available bandwidth is used, that is, bandwidth should only be made available to a queue that actually contains data for transmission, while also ensuring that the traffic queues are each treated “fairly”, taking into account the fact that they need not all be treated equally, but that some queues may be given more bandwidth than others. At the same time, it is preferable that the scheduling method should not itself introduce much additional computational complexity into the system.
The document “A Generalized Processor Sharing Approach to Flow Control in Integrated Services Networks: The Single-Node Case”, Abhay K. Parekh and Robert G. Gallager, IEEE/ACM Transactions on Networking, vol. 1, no. 3, June 1993, pages 344-357, describes the Generalized Processor Sharing method.
However, scheduling methods that emulate the Generalized Processor Sharing method are typically computationally complex, and are therefore usually most suitable for applications with fixed-length data packets, and/or low data rates.